package com.yx.study.leet.questionList.questions;

import org.junit.Test;

/**
 * 45. 跳跃游戏 II
 * https://leetcode.cn/problems/jump-game-ii/
 * 贪心算法
 */
public class Solution45 {
    public int jump(int[] nums) {
        int step = 0; // 步数
        int end = 0; // 当前跳跃边界
        int maxPosition = 0; // 当前能跳跃的最远下标
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, nums[i] + i); // 最远能到达的下标 值+当前下标
            if (i == end) { // 到达此次跳跃的边界
                end = maxPosition;
                step++;
            }
        }
        return step;
    }

    @Test
    public void test() {
        int[] nums = new int[]{2, 3, 1, 1, 4};
        System.out.println(jump(nums));
    }
}
